package LC;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * https://leetcode.com/problems/the-skyline-problem/description/
 * A city's skyline is the outer contour of the silhouette formed
 * by all the buildings in that city when viewed from a distance.
 * Now suppose you are given the locations and height of all the buildings
 * as shown on a cityscape photo (Figure A),
 * write a program to output the skyline formed by these buildings collectively (Figure B).
 */
public class LC_218_TheSkylineProblem {
    public static void main(String[] args) {
        int[][] a = new int[][]{
                {2, 9, 10},
                {3, 7, 15},
                {5, 12, 12},
                {15, 20, 10},
                {19, 24, 8}
        };
        List<int[]> res = Solution.getSkyline(a);
        for (int[] re : res) {
            System.out.println(Arrays.toString(re));
        }
    }

    static class Solution {
        static List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<>();
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, (a, b) -> b - a);
            List<int[]> bl = new ArrayList<>();
            for (int[] building : buildings) {
                bl.add(new int[]{building[0], building[2]});
                bl.add(new int[]{building[1], -building[2]});
            }
            bl.sort((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
            int pre = 0, cur;
            for (int[] b : bl) {
                if (b[1] > 0) {
                    maxHeap.add(b[1]);
                    cur = maxHeap.peek();
                } else {
                    maxHeap.remove(-b[1]);
                    cur = (maxHeap.peek() == null) ? 0 : maxHeap.peek();
                }
                if (cur != pre) {
                    res.add(new int[]{b[0], cur});
                    pre = cur;
                }
            }
            return res;
        }
    }
}